class Solution {
    /**
        拓扑排序: kahn算法,每次删去入度为0的点
        坑点: 不能使用引用类型初始化Arrays.fill
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // edges[i] 表示 点i 可以到达的边
        // 注意不能使用Arrays.fill初始化
        List<Integer>[] edges = new List[numCourses];
        for (int i = 0; i < edges.length; i++) {
            edges[i] = new ArrayList<>();
        }
        // 入度
        int[] input = new int[numCourses];

        for (int[] arr : prerequisites) {
            int u = arr[1], v = arr[0];
            edges[u].add(v);
            input[v]++;
        }

        // 将入度为0的点存放在q中
        Deque<Integer> q = new LinkedList<>();
        for (int i = 0; i < input.length; i++) {
            if (input[i] == 0) {
                q.add(i);
            }
        }

        List<Integer> ans = new ArrayList<>();
        /**
         * 拓扑排序原理: 不断删去入度为0的节点
         */
        while (q.size() > 0) {
            // 删点
            int u = q.removeFirst();
            ans.add(u);
            // 删边
            for (Integer v : edges[u]) {
                input[v]--;
                if (input[v] == 0)
                    q.addLast(v);
            }
        }

        return ans.size() == numCourses;
    }
}

class Solution {
    /**
        拓扑排序：dfs实现
            bok[u]=0 没遍历
            bok[u]=1 遍历中
            bok[u]=2 已遍历

            核心思想是判断是否有环,对u的子节点遍历, 如果u还没有遍历完(bok[u]==1) 
            同时被它的子节点遍历到了, 那就存在环

     */
    List<Integer>[] edges;
    int[] bok;
    boolean ans = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // edges[i] 表示 点i 可以到达的边
        edges = new List[numCourses];
        for (int i = 0; i < edges.length; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int[] arr : prerequisites) {
            int u = arr[1], v = arr[0];
            edges[u].add(v);
        }

        bok = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (bok[i] == 0 && ans)
                dfs(i);
        }
        
        return ans;
    }

    public void dfs(int u) {
        if (ans == false) { // 剪枝
            return;
        }
        bok[u] = 1;
        for (int v : edges[u]) {
            if (bok[v] == 0) {
                dfs(v);
            } else if (bok[v] == 1) {  // 如果u的子节点还没有遍历完 又被其他节点遍历 那么存在环
                ans = false;
            }
        }
        bok[u] = 2; // u子节点遍历完毕
    }
}